import java.util.Random;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86186
 * Date: 2023-09-04
 * Time: 10:53
 */
public class Test {
    private void swap(int[] nums,int x, int y) {
        int tmp = nums[x];
        nums[x] = nums[y];
        nums[y] = tmp;
    }

    //leetcode 75 颜色分类
    public void sortColors(int[] nums) {
        //通过三个指针 left、i、right 将数组分为四个部分
        //[0,left]表示为0的部分
        //[left + 1,i - 1] 表示为1的部分
        //[i,right-1]表示待排序的部分
        //[right,n-1]表示为2的部分
        int n = nums.length;
        int left = -1,right = n;
        int i = 0;
        while(i < right) {
            if(nums[i] == 0) {
                swap(nums,++left,i++);
            }else if(nums[i] == 1) {
                i++;
            }else {
                swap(nums,--right,i);
            }
        }
    }

    //leetcode 912 快速排序
    public int[] sortArray(int[] nums) {
        qsort(nums,0,nums.length-1);
        return nums;
    }

    //递归实现分冶排序
    private void qsort(int[] nums, int l, int r) {
        if(l >= r) return;
        Random random = new Random();
        int key = nums[random.nextInt(r - l + 1) + l];
        int left = l - 1, right = r + 1, i = l;
        while(i < right) {
            if(nums[i] < key) swap(nums,++left,i++);
            else if(nums[i] == key) i++;
            else swap(nums,--right,i);
        }
        qsort(nums,l,left);
        qsort(nums,right,r);
    }

    //leetcode 215 数组中第k个最大的元素
    public int findKthLargest(int[] nums, int k) {
        return qsort(nums,0,nums.length-1,k);
    }

    private int qsort(int[] nums, int l, int r, int k) {
        int key = nums[new Random().nextInt(r - l + 1) + l];
        int left = l-1, right = r + 1, i = l;
        while(i < right) {
            if(nums[i] < key) swap(nums,++left,i++);
            else if(nums[i] == key) i++;
            else swap(nums,--right,i);
        }
        //c表示大于key的部分，b表示等于key的部分，剩下的部分就是小于key的部分
        int c = r - right + 1;
        int b = right - left - 1;
        if(c >= k) return qsort(nums,right,r,k);
        else if(b + c >= k) return key;
        else return qsort(nums,l,left,k - b - c);
    }

    //剑指offer40 最小的k个数
    public int[] getLeastNumbers(int[] arr, int k) {
        qsort1(arr,0,arr.length-1,k);
        int[] ret = new int[k];
        for(int i = 0; i < k; i++) {
            ret[i] = arr[i];
        }
        return ret;
    }

    private void qsort1(int[] nums, int l, int r, int k) {
        int key = nums[new Random().nextInt(r - l + 1) + l];
        int left = l - 1, right = r + 1,i = l;
        while(i < right) {
            if(nums[i] < key) swap(nums,++left,i++);
            else if(nums[i] == key) i++;
            else swap(nums,--right,i);
        }
        int a = left - l + 1, b = right - left - 1;
        if(a > k) qsort(nums,l,left,k);
            //因为b部分中的数据都是等于key的值，所以前k小的数就已经排好序了，可以直接返回
        else if(a + b >= k) return;
        else qsort(nums,right,r,k - a - b);
    }
}
